package org.leetcode.middle.leetcode287;

import java.util.HashSet;

public class Solution {



    public int findDuplicate2(int[] nums){

        int slow = 0,fast=0;

        while (true){
            slow=nums[slow];
            fast=nums[nums[fast]];
            if (slow==fast){
                break;
            }
        }

        slow =0;

        while (slow!=fast){
            slow=nums[slow];
            fast=nums[fast];
        }

        return fast;
    }


    //不符合题意，空间复杂度不为O(1)
    public int findDuplicate(int[] nums){

        HashSet<Integer> hashSet = new HashSet<>();

        for (int num:nums) {
            if (hashSet.contains(num)) {
                return num;
            }else {
                hashSet.add(num);
            }
        }

        return 2;
    }

}
